/**
 * @author ChaP
 * @date 2019/05/24
 * @describe:
 */
package CodingTest.AC20190524;

import java.util.Stack;

/**leetcode - 456
 * 给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。

 注意：n 的值小于15000。

 示例1:

 输入: [1, 2, 3, 4]

 输出: False

 解释: 序列中不存在132模式的子序列。
 示例 2:

 输入: [3, 1, 4, 2]

 输出: True

 解释: 序列中有 1 个132模式的子序列： [1, 4, 2].
 示例 3:

 输入: [-1, 3, 2, 0]

 输出: True

 解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].
 */
public class find132pattern {
    //方法一：n2
    public boolean find132pattern(int[] nums){
        if(nums.length <3) return false;
            for(int i =0;i<nums.length;i++){
                int max = Integer.MIN_VALUE;
                for(int j = i;j<nums.length;j++){
                    if(nums[j]>max){
                        max = nums[j];
                    }
                    if(nums[j]<max && nums[j]>nums[i] &&nums[i]<max){
                        return true;
                    }
                }
            }
            return false;
    }
    //方法二：栈方法
    public boolean find132pattern1(int[] nums){
        //third是第三个元素即 132中2 栈和third维护32，且保持2最大，所以
        //每当nums[i]时维护nums[i]最大，即使nus不断更新，即每次入栈如果栈顶元素小于入栈元素，则把栈顶
        //元素赋给third
        int third = Integer.MIN_VALUE;
        Stack<Integer> s = new Stack<>();
        for(int i = nums.length-1;i>=0;i--){
            if(nums[i] < third) return true;
            while(!s.isEmpty() && nums[i]>s.peek()){
                third = s.pop();

            }
            s.push(nums[i]);
        }
        return false;
    }
}
